Convolutional codes, error detection codes, error correction codes or combined error detection/correction codes, and the use of a Viterbi decoder as a maximum likelihood decoder for convolutional codes are well known in the art.
In the transmitter of an illustrative data transmission system, a convolutional encoder proceeds through a sequence of states as it accepts data bits and produces output that subsequently is used to define an output sequence of symbols that is transmitted over a (noisy or otherwise impaired) channel. The output sequence of symbols corresponds to a path through the trellis that describes that encoder operation.
In the receiver, a Viterbi decoder determines the output sequence of data bits that was transmitted based on the received corrupted version of the transmitted sequence of symbols and knowledge of the code used by the encoder. The output sequence corresponds to the "best path", that is, the single path through the trellis having the best so-called path metric. For the Gaussian channel, for example, the determination of the output sequence is made by correlating with the received version all possible transmitted sequences (corresponding to paths through the trellis) and then choosing, as the "maximum likelihood" sequence, the sequence where the correlation is maximum.
Also known in the art is a group of extended Viterbi algorithms referred to as the List Viterbi algorithms. Whereas the "regular" Viterbi algorithm described above identifies the single best path through the trellis, a List Viterbi algorithm identifies the L best paths, or L best candidates, through the trellis. (The case in which L=1 is the regular Viterbi algorithm.) Versions of the List Viterbi algorithms produce a rank ordered list of the L best candidate decodings corresponding to a block of convolutional coded data. See, for example, our co-pending, commonly-assigned applications, U.S. Pat. application Ser. No. 09/055,082 entitled "List Viterbi Algorithms for Continuous Data Transmission" and U.S. Pat. application Ser. No. 09/054,676 entitled "List Viterbi Algorithms for Tailbiting Convolutional Codes" filed concurrently herewith; U.S. Pat. No. 5,208,816, issued May 4, 1993 to Seshadri and Sundberg; and U.S. Pat. No. 5,537,444 issued Jul. 16, 1996 to Nill and Sundberg.
List Viterbi algorithms are particularly effective in performing error detection/correction for convolutionally encoded data. As an example, consider a system in which a block of data to be transmitted is coded by a first, so-called outer code followed by a second, so-called inner code, where the outer code is an error detecting code and the inner code is a convolutional code. In the receiver, the decoder for the inner code is the first to operate on the received signal and it releases to the outer decoder the best decoded sequence based on the Viterbi algorithm. The outer decoder performs error detection on the best decoded sequence and, if an error is detected, may use error mitigation techniques in an attempt to repair the detected error. Such techniques may only be able to repair the error approximately, however.
On the other hand, if a List Viterbi algorithm is utilized, the L best decoded sequences can be provided, thereby eliminating the need for potentially erroneous error mitigation. In particular, if an error is detected, the second best of the L decoded sequences is tried. If it too has an error, the third best is tried, and so forth until one of the L decoded sequences satisfies the error code.
Although there is always the possibility that the decoded sequence released by the outer decoder has an error that the outer decoder did not detect, the likelihood of this occurring may be somewhat increased in those systems in which a List Viterbi algorithm is used. This is due in part to the fact that the sequence that satisfies the outer decoder may not be the first best of the L sequences identified by the List Viterbi algorithm. That is, although this sequence may satisfy the outer decoder, the List Viterbi decoder had determined that it was not the best sequence corresponding to the sequence that was transmitted and, therefore, the sequence may in fact have errors that escaped detection by the outer decoder.
Undetected errors in a sequence released by the outer decoder may be problematic in, for example, digital audio data transmission systems, such as Digital Audio Broadcasting systems. In such systems, if the outer decoder, for example, a Cyclic Redundancy Check ("CRC") decoder, detects no error in the sequence provided by the Viterbi decoder, it releases the CRC-decoded sequence to an audio decoder and subsequently an analog audio signal corresponding to the released sequence is generated. On the other hand, if the CRC decoder detects an error in the sequence provided to it, an error flag is raised, thereby initiating audio decoder error mitigation routines. The error mitigation routines may provide, for example, for the substitution by an error mitigation signal for the audio signal that would correspond to the sequence in error. However, if a CRC error is not detected, no error flag is raised and the CRC-decoded sequence containing the error is released to the audio decoder, possibly causing significant errors in the resulting analog audio signal.
Increasing the number of error code bits for a block of information may alleviate this problem but results in a decreased information bit rate, given that the channel bandwidth is fixed. Thus, for transmission systems that utilize a List Viterbi algorithm, it would be advantageous to be able to further examine, or "screen", the sequences that were found to satisfy an error code but which may contain an error undetected by the outer decoder.